
import random


class NonComparisonSort:
    """
    非比较排序算法类，包括计数排序、桶排序和基数排序的实现。
    """

    @staticmethod
    def counting_sort(arr):
        """
        计数排序算法的核心思想是通过统计每个元素的出现次数，然后根据计数结果重新构建有序序列。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：计数排序中，相同元素的相对顺序不会改变。
        """
        # 如果输入列表为空，则直接返回空列表
        if len(arr) == 0:
            return []

        # 步骤 1: 确定待排序列表的范围
        max_val = max(arr)
        min_val = min(arr)
        range_val = max_val - min_val + 1

        # 步骤 2: 统计每个元素的出现次数
        count = [0] * range_val
        for num in arr:
            count[num - min_val] += 1

        # 步骤 3: 累加计数列表
        for i in range(1, range_val):
            count[i] += count[i - 1]

        # 步骤 4: 构建有序序列
        sorted_arr = [0] * len(arr)
        for num in reversed(arr):
            index = count[num - min_val] - 1
            sorted_arr[index] = num
            count[num - min_val] -= 1

        return sorted_arr


    @staticmethod
    def bucket_sort(arr, num_buckets=10):
        """
        桶排序算法的核心思想是将待排序的元素分布到不同的桶中，然后对每个桶进行排序，并按顺序将桶中的元素合并得到有序序列。

        参数：
        arr (list): 待排序的列表。
        num_buckets (int): 桶的数量，默认为 10。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：桶排序中，相同元素的相对顺序不会改变。
        """
        # 步骤 1: 创建桶并分布元素
        min_val = min(arr)
        max_val = max(arr)
        bucket_range = (max_val - min_val + 1) / num_buckets

        buckets = [[] for _ in range(num_buckets)]
        for num in arr:
            index = int((num - min_val) // bucket_range)
            buckets[index].append(num)

        # 步骤 2: 对每个桶中的元素进行排序
        for i in range(num_buckets):
            buckets[i] = NonComparisonSort.counting_sort(buckets[i])

        # 步骤 3: 合并桶中的元素
        sorted_arr = []
        for bucket in buckets:
            sorted_arr.extend(bucket)

        return sorted_arr


    @staticmethod
    def radix_sort(arr):
        """
        基数排序算法的核心思想是根据元素的每个位上的值，进行多次按位排序，直到所有位都排好序。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：基数排序中，相同元素的相对顺序不会改变。
        """
        # 步骤 1: 确定最大值的位数
        max_val = max(arr)
        max_digits = len(str(max_val))

        # 步骤 2: 按位进行排序
        for i in range(max_digits):
            # 创建 10 个桶，用于存放当前位上的元素
            buckets = [[] for _ in range(10)]

            # 将元素分配到对应的桶中
            for num in arr:
                digit = (num // (10 ** i)) % 10
                buckets[digit].append(num)

            # 合并桶中的元素
            arr = [num for bucket in buckets for num in bucket]

        return arr


# 主程序
if __name__ == "__main__":
    # 生成随机输入列表
    input_list = random.sample(range(1, 101), 10)
    print("随机输入列表:", input_list)

    # 创建 NonComparisonSort 对象
    sorter = NonComparisonSort()

    # 调用计数排序方法进行排序
    sorted_list_counting = sorter.counting_sort(input_list)
    print("计数排序后的列表:", sorted_list_counting)  # 计数排序后的列表: [1, 2, 4, 5, 7]

    # 调用桶排序方法进行排序
    sorted_list_bucket = sorter.bucket_sort(input_list)
    print("桶排序后的列表:", sorted_list_bucket)  # 桶排序后的列表: [1, 2, 4, 5, 7]

    # 调用基数排序方法进行排序
    sorted_list_radix = sorter.radix_sort(input_list)
    print("基数排序后的列表:", sorted_list_radix)  # 基数排序后的列表: [1, 2, 4, 5, 7]
